/*
 * kSmallInTwoSortedArray.cpp
 *
 *  Created on: Sep 11, 2012
 *      Author: jeffrey
 */
#include<iostream>
#include<limits>
using namespace std;
class KSmallIn2SortedArray {
public:
	static int ksmall(int a[], int alen, int b[], int blen, int k) {
		if (k < 1 || k > alen + blen)
			return numeric_limits<int>::min();
		return findKSmall(a, 0, alen - 1, b, 0, blen - 1, k);
	}
private:
	static int findKSmall(int a[], int as, int ae, int b[], int bs, int be,
			int k) {
		if (bs > be)
			return a[as + k - 1]; // if b is empty, in array a
		if (as > ae)
			return b[bs + k - 1]; // if a is empty, in array b
		int i = (ae - as + 1) / (double) (ae - as + be - bs + 2) * k;
		int j = k - 1 - i;
		i += as;
		j += bs;
		int ai = i == ae + 1 ? numeric_limits<int>::max() : a[i];
		int ai_1 = i == as ? numeric_limits<int>::min() : a[i - 1];
		int bj = j == be + 1 ? numeric_limits<int>::max() : b[j];
		int bj_1 = j == bs ? numeric_limits<int>::min() : b[j - 1];
		if (bj >= ai_1 && bj <= ai) // bj in [ai_1,ai],
			return bj;
		if (ai >= bj_1 && ai <= bj) // ai in [bj_1,bj],
			return ai;
		if (ai <= bj)
			return findKSmall(a, i + 1, ae, b, bs, j - 1, k - (i - as + 1));
		else
			return findKSmall(a, as, i - 1, b, j + 1, be, k - (j - bs + 1));
	}
};
//int main() {
//	int a[] = { 1, 4, 6, 9, 10, 12 };
//	int b[] = { 2, 4, 7, 13, 15, 16, 18 };
//
//	for (int i = 1; i < 12; i++)
//		cout << KSmallIn2SortedArray::ksmall(a, 6, b, 7, i) << endl;
//
//}

